package chapter2;

/**
 * 算法基础-选择排序
 * <p>
 * 原址排序-最坏/平均O(n^2)
 */
public class SelectSort {

    public static void selectSort(int[] A) {
        // 每次选择一个最小的数字,从该位置开始往后遍历,如果有更小的则拿出来,与当前位置进行交换
        for (int i = 1; i < A.length; i++) {
            // 选择最小数
            int min = A[i - 1];
            int index = i - 1;
            for (int j = i; j < A.length; j++) {
                if (min > A[j]) {
                    index = j;
                    min = A[j];
                }
            }
            // 交换
            int temp = A[i - 1];
            A[i - 1] = A[index];
            A[index] = temp;
        }
    }

}
